class Solution
{
public:
    // 尝试从不重复的子数组合并，答案不对
    class Wrong
    {
        int minCost(vector<int> &nums, int k)
        {

            int n = nums.size();
            int noCutLen = trimmedLen(nums, 0, n);
            if (k >= n)
            {
                return k + noCutLen;
            }

            vector<int> noRepeatGroupsIndex{0};
            unordered_set<int> groupSet;
            int i = 0;
            while (i < n)
            {
                if (groupSet.count(nums[i]))
                {
                    noRepeatGroupsIndex.push_back(i);
                    groupSet.clear();
                }
                else
                {
                    groupSet.insert(nums[i]);
                }
                ++i;
            }
            noRepeatGroupsIndex.push_back(n);
            vector<int> &groupIndex = noRepeatGroupsIndex;

            int groupCount = noRepeatGroupsIndex.size() - 1;
            int curGroup = 0;
            while (curGroup < groupCount - 1)
            {
                if (mergeCost(nums, groupIndex[curGroup], groupIndex[curGroup + 1], groupIndex[curGroup + 2]) <= k)
                {
                    groupIndex.erase(groupIndex.begin() + curGroup + 1);
                    --groupCount;
                }
                else
                {
                    ++curGroup;
                }
            }

            int totalCost = 0;
            for (int group = 0; group < groupIndex.size() - 1; ++group)
            {
                totalCost += k + trimmedLen(nums, groupIndex[group], groupIndex[group + 1]);
            }
            return totalCost;
        }

        int trimmedLen(vector<int> &nums, int begin, int end)
        {
            int len = 0;
            unordered_map<int, int> numCount;
            for (int i = begin; i < end; ++i)
            {
                int num = nums[i];
                if (numCount[num] == 1)
                {
                    len += 2;
                }
                else if (numCount[num] > 1)
                {
                    ++len;
                }
                ++numCount[num];
            }
            return len;
        }

        int mergeCost(vector<int> &nums, int begin1, int end1, int end2)
        {
            int subLen1 = trimmedLen(nums, begin1, end1);
            int subLen2 = trimmedLen(nums, end1, end2);
            int totalLen = trimmedLen(nums, begin1, end2);
            return totalLen - subLen1 - subLen2;
        }
    };
};